﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.Closures
{
	public class MatrixTransitiveClosureFinder : IMatrixTransitiveClosureFinder
	{
	    private readonly Func<IEnumerable<IEnumerable<bool>>, bool[][]> _createMatrix;

	    public MatrixTransitiveClosureFinder(Func<IEnumerable<IEnumerable<bool>>,bool[][]> createMatrix = null)
	    {
	        _createMatrix = createMatrix ?? (it => (from e in it
	                                                select e.ToArray()).ToArray());
	    }

	    private bool[][] SquareAndAddition(bool[][] matrix)
	    {
	        bool[][] result = _createMatrix(matrix);
	        int n = matrix.Length;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    for (int k = 0; k < n; k++)
                        result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
	        return result;
	    }

	    public bool[][] TransitiveClosure(bool[][] matrix)
	    {
	        int i = 1;
	        int n = matrix.Length;
	        bool[][] result = matrix;
            while ( i <= n )
            {
                result = SquareAndAddition(result);
                i *= 2;
            }
	        return result;
	    }
	}
}
